package demo;
import java.util.Arrays;

public class Sort {

    // 冒泡排序
     public static void bubbleSort(int[] array){
       int size= array.length;
       for(int i=0;i<size-1;i++){
           //无序区间 [0,size-i )
           //有序区间  [size-i  ,size)
           boolean sort=true;
           for(int j=0;j<size-i-1;j++){
               if(array[j]>array[j+1]){
                   swap(array,j,j+1);
                   sort=false;
               }
           }
          if(sort=true){
              return ;
          }
       }

    }

// 快速排序
     public static void quickSort(int[] array){
         quickSortWithRange(array,0,array.length-1);
    }
    private static void quickSortWithRange(int[]arr,int fromIndex,int toIndex){
         int size=toIndex-fromIndex+1;
         if(size<=1){
             return ;
         }
         int pivotIndex=partition(arr,fromIndex,toIndex);
         quickSortWithRange(arr,fromIndex,pivotIndex-1);
         quickSortWithRange(arr,pivotIndex+1,toIndex);
    }
    private static int partition(int[]arr,int fromIndex,int toIndex){
         int leftIndex=fromIndex;
         int rightIndex=fromIndex;

         int pivot=arr[toIndex];

         while(rightIndex<toIndex){

            if(arr[rightIndex]>=pivot){
                 rightIndex++;
             }
           else{
               swap(arr,leftIndex,rightIndex);
               leftIndex++;
               rightIndex++;
           }
         }
        swap(arr,leftIndex,rightIndex);
         return leftIndex;
    }

    private static void swap(int[]array,int i,int j){
         int temp=array[i];
         array[i]=array[j];
         array[j]=temp;

    }
    public static void main(String[] args) {
        int[]arr={1,5,3,7,4,5,1,9,5};
        int[]arr2=arr;
        System.out.println("冒泡排序：");
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("--------");
        quickSort(arr2);
        System.out.println("快速排序：");
        System.out.println(Arrays.toString(arr2));
    }
}
